package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC75 {
    public void sortColors(int[] nums) {
        int left = -1, right = nums.length, cur = 0;
        while (cur < right) {
            if (nums[cur] == 1) {
                cur++;
            } else if (nums[cur] == 0) {
                swap(nums, cur++, ++left);//this because that left we make it alwasy less or equal than
                // cur, and if num[++left] only could be 1, no possible 0, so can be switch directly.
            } else if (nums[cur] == 2) {
                swap(nums, cur, --right);
            }
        }
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public static void main(String[] args) {
        LC75 an = new LC75();
        int[] arr = {2, 0, 2, 1, 1, 0};
        an.sortColors(arr);
    }
}
